package com.example.backtrack;

import java.util.*;

/**
 * 39. 组合总和
 * 给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
 * <p>
 * candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
 * <p>
 * 对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
 * <p>
 * 示例 1：
 * <p>
 * 输入: candidates = [2,3,6,7], target = 7
 * 输出: [[7],[2,2,3]]
 * <p>
 * 思路：这个题和本来的组合的区别是没有了目标元素数量的控制，换为了目标和。所以并入res的条件就变为了目标和
 * 这个题的另一个特色是不限制元素使用次数，所以在遍历的时候 一直用的是start
 */
public class CombinationSum {
    List<List<Integer>> res = new ArrayList();
    Deque<Integer> path;
    int[] candidates;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        path = new LinkedList<>();
        Arrays.sort(candidates);//排序是为了剪枝
        back(0, target);
        return res;
    }

    public void back(int start, int target) {
        //在这控制target<=0return 也可以，就是会多走很多流程，如多余的在path中添加删除元素
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            int candidate = candidates[i];
            if (target - candidates[i] < 0) break;//在这里剪枝防止把多余元素加入path
            target -= candidate;
            path.add(candidate);
            back(i, target);
            target += path.removeLast();
        }
    }
}
